function quicksort (arr, start = 0, end = arr.length - 1) {
  if (start == end) return arr
  let index = partition(arr, start, end);
  if (index > start) {
    quicksort(arr, start, index - 1);
  }
  if (index < end) {
    quicksort(arr, index + 1, end)
  }
}
function partition (arr, start, end) {
  let pivot = Math.floor(Math.random(end - start) + start);
  [arr[pivot], arr[end]] = [arr[end], arr[pivot]]
  let small = start - 1;
  for (let index = start; index < end; ++index) {
    if (arr[index] < arr[end]) {
      small++;
      if (index !== small) {
        [arr[index], arr[small]] = [arr[small], arr[index]]
      }
    }
  }
  small++;
  [arr[small], arr[end]] = [arr[end], arr[small]];
  return small
}